package graph 
{
	import data.*;
	
	/**
	 * A graph representing available travel paths in the game. Graph is undirected, at most
	 * one edge between any two nodes
	 */
	public class GCTravelGraph 
	{
		// All city nodes in this graph
		private static var _totalNodes:Vector.<GCNode>;
		
		private static var _graphInstance:GCTravelGraph;
		
		public function GCTravelGraph() 
		{
			_totalNodes = new Vector.<GCNode>();
			
			for (var i:uint = 0; i < GCCityData.NUM_CITIES; i++)
			{
				var cityNode:GCNode = new GCNode(i);
				_totalNodes.push(cityNode);
			}
			
			// Go through each path, add appropriate neighbors for each city node
			// and costs
			for each (var path:GCPathDataStruct in GCPathData.pathInformation)
			{
				var firstCity:GCNode = _totalNodes[path._cityA];
				var secondCity:GCNode = _totalNodes[path._cityB];
				var stats:Vector.<uint> = path._requiredStats;
				
				firstCity.addNeighbor(secondCity, stats);
				secondCity.addNeighbor(firstCity, stats);
			}
		}
		
		public static function getInstance():GCTravelGraph
		{
			if (_graphInstance == null)
			{
				_graphInstance = new GCTravelGraph();
			}
			
			return _graphInstance;
		}
		
		public function initializeTravelCosts():void
		{
			// Perform BFS with each node as the root to correctly calculate the minimum requirements
			// to get from one city to any other city
			for each (var cityNode:GCNode in _totalNodes)
			{
				performBFS(cityNode);
			}
		}
		
		/**
		 * Function to perform Breadth-First Search starting a given root
		 * 
		 * Requirements are pessimistic, always require the maximum requirements
		 * 
		 * @param	root
		 */
		public function performBFS(root:GCNode):void
		{
			// Reset all nodes to be unvisited
			for each (var cityNode:GCNode in _totalNodes)
			{
				cityNode.visited = false;
			}
			
			var departureCityId:uint = root.cityId;
			
			var queue:Vector.<GCNode> = new Vector.<GCNode>();
			root.visited = true;
			queue.push(root);
			
			while (queue.length != 0)
			{
				// The node from which we are traveling to the next hop
				var node:GCNode = queue.shift();
				
				// The stats to get from the departure city to this next node
				// which we are examining
				var statsFromDepartureCity:Vector.<uint> = node.statsToReach[departureCityId];
				
				// Go through each neighbor
				for each (var neighbor:GCNeighborStruct in node.neighbors)
				{
					var otherNode:GCNode = neighbor.neighborNode;
					
					if (!otherNode.visited)
					{
						queue.push(otherNode);
					}
					
					otherNode.visited = true;
					
					// This is the requirement to enter the city from the previous one
					// Not the same as the original intended departure node
					var travelToPathRequirement:Vector.<uint> = neighbor.statsRequirement;
					
					// If stats to get to this node from departure point is not set...
					// In any case we compare the cost of the extra path
					var statsToUse:Vector.<uint>;
					if (otherNode.statsToReach[departureCityId] == null)
					{
						//trace("Calculating stat requirements to reach this city from " + departureCityId);
						statsToUse = travelToPathRequirement.concat();
						
						// Set the stat requirement to reach that neighbor from the
						// root city
						for (var i:uint = 0; i < GCShipData.NUM_STATS; i++)
						{
							// Compare travel requirement of the next hop, to the requirement
							// to the hop before. Uses the larger of the two.
							statsToUse[i] = Math.max(statsToUse[i], statsFromDepartureCity[i]);
						}
						
						otherNode.statsToReach[departureCityId] = statsToUse;
						//trace("Cost " + GCCityData.getNameFromId(departureCityId) + " " + GCCityData.getNameFromId(otherNode.cityId) + " " + statsToUse.toString());
					}
					else
					{
						// Already have a cost to reach here, don't really need to 
						/*
						statsToUse = otherNode.statsToReach[departureCityId];
						for (var i:uint = 0; i < GCShipData.NUM_STATS; i++)
						{
							// Compare travel requirement of the next hop, to the requirement
							// to the hop before. Uses the larger of the two.
							statsToUse[i] = Math.max(statsToUse[i], travelToPathRequirement[i]);
						}
						*/
					}
				}
			}
		}
		
		/**
		 * Not entirely correct, there might be an alternate path the player can use, but right now it is
		 * too difficult to statically store all possible paths. We just pick the first path BFS sees as the one to use
		 * 
		 * @param	departureCity
		 * @param	destinationCity
		 * @param	currentStats
		 */
		public function canReachCity(departureCity:uint, destinationCity:uint, currentStats:Vector.<uint>):Boolean
		{
			var destinationNode:GCNode = _totalNodes[destinationCity];
			var neededStats:Vector.<uint> = destinationNode.statsToReach[departureCity];
			
			for (var i:uint = 0; i < GCShipData.NUM_STATS; i++)
			{
				
				// If there is a deficient stat, return that the destination cannot be reached
				if (currentStats[i] < neededStats[i])
				{
					return false;
				}
			}
			//trace("can reach " + GCCityData.getNameFromId(departureCity) + " " + GCCityData.getNameFromId(destinationCity));
			return true;
		}
	}

}